The invention relates to a method for controlling a movement of a guided object in an environment to avoid collision with another object. The method comprises making predictions of a collision ahead of occurrence of the collision, given the geometrical outlines of all objects involved, their relative positions, and their trajectories in an immediate future. Each object is represented by at least one spherical bubble of known radius and centre position. The bubble contains at least partially the geometrical outline of the object. At least one object is represented by a cluster of interpenetrating spherical bubbles of at least two different radii. The outermost surface of the cluster contains the outermost surface of the object. The collision between objects is predicted as a first estimated point of touch to occur between any bubble of the cluster with a bubble representing another object. Such a method is known from European Patent Application 87198, U.S. Pat. No. 4,578,757 which is incorporated herein by reference.
In considering the problem of collision prediction, it might be assumed that it would be helpful to restrict the shape of objects so that all objects were built up from simple geometric solids i.e. blocks, cylinders and spheres. On closer examination, however, it turns out that, while these primitive shapes are simple in a geometric sense, collisions between these shapes are surprisingly complex. For example in a collision between a cube and a cylinder, the following five distinct kinds of collision are possible.
(1) Corner point hits planar surface.
(2) Corner point hits curved surface.
(3) Edge line hits curved surface.
(4) Edge line hits circular edge line.
(5) Planar face hits circular edge line.
Other very unlikely kinds of collision, such as a vertex of the cube hitting a circular edge line of the cylinder are regarded as limiting cases of one of the above kinds of collision.
The reference provides a simple, regular, general way of representing the shape of an object which simplifies the collision prediction.
Thus the collision problem reduces to finding the earliest pair of bubbles to collide. The time and place of a collision between two bubbles can be found easily and exactly provided both bubbles are travelling with uniform velocity. The time at which the collision occurs is found by solving a quadratic equation having time as the independent variable. This equation has two roots. If they are imaginary, no collision occurs. Otherwise, the roots correspond to two times, and the earlier of these is the required answer. The later time is the time at which the bubbles would part again supposing that, instead of behaving like solid objects and colliding, they had passed through each other without deviating from their courses.
Objects may not travel at uniform velocity because they can rotate and are subject to gravity and other forces. However, the constant velocity assumption may be sufficient for short-term predictions, which is the main concern in simulating the relative movement of objects.
The representation of an object may be effected fully or partly. In the latter case the representation must be done as far as necessary, in that an actual collision would always be preceded by a collision with a representing bubble. In practice, one object could be represented by a single bubble. Alternatively, both or all objects are represented by a cluster of a plurality of bubbles.
The prediction of the collision of two clusters of bubbles will involve a computation time proportional to the product of the numbers of bubbles in the two clusters. If there are 100 bubbles in each of two clusters, then 10,000 computations are needed.